---
title: "L2-025 分而治之"
created: 2025-11-28
tags:
  - 算法
---

# L2-025 分而治之

## 题目 [L2-025 分而治之](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805056195379200&page=1)

![[image-27ec8074.png]]

## 思路分析

无向图 邻接矩阵存

将一些点的联系斩断

看是否变为全0矩阵即可

![[image-428d585f.png]]

既然邻接矩阵爆空间 那就用邻接表优化空间

## 代码实现

15/25

```typescript
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};
const int inf = 0x3f3f3f3f;
priority_queue<int> pq;
multiset<int> s;

vector<vector<int>> g;
int n,m;//n城市数 m道路数

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	g.resize(n+1,vector<int>(n+1));
	while(m--) {
		int a,b;
		cin>>a>>b;
		g[a][b]=g[b][a]=1;
	}
//	for(int i=1; i<=n; i++) {
//		for(int j=1; j<=n; j++) {
//			cout<<g[i][j]<<" ";
//		}
//		cout<<endl;
//	}
//	cout<<endl;
	int k;
	cin>>k;
	while(k--) {
		vector<vector<int>> copy=g;
		int np;
		cin>>np;
		for(int i=1; i<=np; i++) {
			int v;
			cin>>v;
			for(int i=1; i<=n; i++) {
				copy[v][i]=copy[i][v]=0;
			}
		}
		bool win=true;
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(copy[i][j]==1){
					win=false;
					break;
				}
			}
			if(!win){
				break;
			}
		}
		if(win)	cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}

	return 0;
}
```

邻接矩阵爆空间 用邻接表优化

```cpp
#include<bits/stdc++.h>

using namespace std;

#define int long long

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};

const int inf = 0x3f3f3f3f;

priority_queue<int> pq;

multiset<int> s;

vector<vector<int>> g;

int n,m;//n城市数 m道路数

signed main() {

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	g.resize(n+1);

	while(m--) {

		int a,b;cin>>a>>b;

		g[a].push_back(b);

		g[b].push_back(a);

	}

//	for(int i=1; i<=n; i++) {

//		for(int j=1; j<=n; j++) {

//			cout<<g[i][j]<<" ";

//		}

//		cout<<endl;

//	}

//	cout<<endl;

	int k;

	cin>>k;

	while(k--) {

		vector<bool> attacked(n+1,false);

		int np;cin>>np;

		for(int i=1; i<=np; i++) {

			int v;cin>>v;

			attacked[v]=true;

		}

		bool win=true;

		for(int u=1; u<=n; u++) {

			if(attacked[u])	continue;

			for(auto v:g[u]) {

				if(!attacked[v]){

					win=false;

					break;

				}

			}

			if(!win){

				break;

			}

		}

		if(win)	cout<<"YES"<<endl;

		else cout<<"NO"<<endl;

	}

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-024 部落|L2-024 部落]] 🏠 [[00-天梯赛]] ➡️ [[L2-026 小字辈|L2-026 小字辈]]